package Sequence;

public class Test0654 {
    public static void main(String[] args) {
        new Solution0654_1().constructMaximumBinaryTree(new int[]{3,2,1,6,0,5});
    }
}

class Solution0654_1 {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        TreeNode ans=new TreeNode(nums[0]),rr=ans;
        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];
            TreeNode treeNode = new TreeNode(num);
            if (num>ans.val) {
                treeNode.left=ans;
                ans=treeNode;
            } else{
                if (num < rr.val) {
                    rr.right=treeNode;
                }else {
                    TreeNode temp=ans;
                    while (temp.right.val>num) temp=temp.right;
                    treeNode.left=temp.right;
                    temp.right=treeNode;
                }
            }
            rr=treeNode;
        }

        return ans;
    }
}
